package Leetcode.排序;

import Leetcode.动态规划.股票最大利润;
import Leetcode.搜索与回溯.全排列;

import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Queue;

/**
 * @ClassName 快排
 * @since: 2023/7/29 16:32
 * @auth: kirito
 * @description:
 **/
public class 快排 {

//    https://zhuanlan.zhihu.com/p/635275297
    public static void Quicksort(int[] array, int start, int end) {
        if (start >= end) {
            return;
        }
        int left = start, right = end;
        int p = array[left];
        while (left < right) {
            while (left < right && array[right] >= p) {
                right--;
            }
            if (left < right) {
                SortUtils.swap(array,left,right);
            }
            while (left < right && array[left] <= p) {
                left++;
            }
            if (left < right) {
                SortUtils.swap(array,left,right);
            }
        }
        SortUtils.swap(array, left, right);
        Quicksort(array, start, left - 1);
        Quicksort(array, left + 1, end);
    }
    public static void quickSort(int[] arr, int start, int end) {
        // 递归结束条件:start大于或等于end时
        if (start < end) {
            // 得到基准元素位置
            int pivotIndex = partition(arr, start, end);
            // 根据基准元素，分成两部分进行递归排序
            quickSort(arr, start, pivotIndex - 1);
            quickSort(arr, pivotIndex + 1, end);
        }
    }
    private static int partition(int[] arr, int start, int end) {
        // 取第1个位置的元素作为基准元素
        int pivot = arr[start];
        int left = start;
        int right = end;

        while (left < right) {
            //right指针左移
            while (left < right && arr[right] >= pivot) {
                right--;
            }
            //left指针右移
            while (left < right && arr[left] <= pivot) {
                left++;
            }
            if (left >= right) {
                break;
            }
            //交换left和right 指针所指向的元素
            SortUtils.swap(arr, left, right);
        }
        // 将基准元素与指针重合点所指的元素进行交换
        arr[start] = arr[left];
        arr[left] = pivot;

        return left;
    }
    //日程表问题
    static int[] arr2 = new int[50];  // 前缀表
    static int[][] arr0;  // 结果数组
    static int[][] arr1;  // 间接结果数组
    static int[][] arr1_;  // 结果数组

    /**
     * 快排思想找第k大数
     */
    public static int find_k_quick(int[] arr, int low, int high, int k) {
        int p = arr[low];
        int low_temp = low, high_temp = high;
        while (low < high) {
            while (low < high && arr[high] <= p) {
                high--;
            }
            SortUtils.swap(arr, low, high);
            while (low < high && arr[low] >= p) {
                low++;
            }
            SortUtils.swap(arr, low, high);
        }
        SortUtils.swap(arr, low, high);
        // 注意，这里k是相对于数组的末尾的索引
        if (low == k) {
            return p;
        } else if (low > k) {
            return find_k_quick(arr, low_temp, low - 1, k);
        } else {
            return find_k_quick(arr, low + 1, high_temp, k);
        }
    }

    /**
     * 打印二维数组（不限制方阵）
     * @param arr 二维数组
     */
    public static void printArr(int[][] arr) {
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr[0].length; j++) {
                System.out.printf("%4d", arr[i][j]);
            }
            System.out.println();
        }
    }
    /**
     * 预处理进入循环赛表获取（只适应于2^k, k>=1）
     * @param n 人数
     * @param start 首位 比如1
     * @param end 尾位 比如8（真实比赛人数）
     */
    public static void tableDoublePrepare(int n, int start, int end) {
        System.out.println("循环赛程表（2^k场景）：");
        arr0 = new int[n][n];
        for (int i = 0; i < n; i++) {
            arr0[i][0] = i;  // 首列赋值
        }
        tableDouble(n, arr0, start, end, end / 2);
    }

    /**
     * 循环赛表获取（只适应于2^k, k>=1）
     * @param n 真实比赛人数
     * @param arr 循环赛表
     * @param start 首位 比如1
     * @param end 尾位 比如8（真实比赛人数）
     * @param disHalf 位差
     */
    private static void tableDouble(int n, int[][] arr, int start, int end, int disHalf) {
        if (start == end - 1) {
            arr[0][start - 1] = arr[1][end - 1] = start;
            arr[0][end - 1] = arr[1][start - 1] = end;
        } else {
            tableDouble(n, arr, start, start + disHalf - 1, disHalf / 2);
            tableDouble(n, arr, end - disHalf + 1, end, disHalf / 2);

            for (int i = 0; i < disHalf; i++) {
                // 对应第一个table
                for (int j = start - 1; j < start + disHalf - 1; j++) {
                    arr[i + disHalf][j + disHalf] = arr[i][j];
                }
                // 对应第二个table
                for (int j = end - disHalf; j < end; j++) {
                    arr[i + disHalf][j - disHalf] = arr[i][j];
                }
            }
        }
    }


    public static void main(String[] args) {
        int[] arr = SortUtils.generateRandomArray_int(10, 1, 10);
        System.out.println(Arrays.toString(arr));

        System.out.println(Arrays.toString(arr));
//        Quicksort(ints,0,arr.length-1);
//        // 要找第5大的数，所以k应该是从末尾开始的第5个索引
//        int k = 10 - 5; // 因为数组是从0开始索引的，所以要减去1
//        System.out.println(find_k_quick(arr, 0, arr.length - 1, k));
//        Arrays.sort(arr);
//        System.out.println(Arrays.toString(arr));
    }

}
